package 单调栈;

import java.util.Stack;

public class LeetCode42_接雨水 {
    public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int length = height.length;
        int i = 0;
        while(i < length) {
            while(!stack.empty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if(stack.empty()) break;
                int w = i - stack.peek() - 1;
                int h = Math.min(height[i],height[stack.peek()]) - height[top];
                ans += h * w;
            }
            stack.push(i++);
        }
        return ans;
    }

}
